package LimitedTimeGame.Day_0225;

/**
 * @author zxc
 * @date 2023/02/25 10:27
 **/

import java.util.HashSet;

/**
 * 题目 ：确定两个字符串是否相近
 * 题目详述 ：
 * 如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：
 * 操作 1：交换任意两个 现有 字符。
 * 例如，abcde -> aecdb
 * 操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。
 * 例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）
 * 你可以根据需要对任意一个字符串多次使用这两种操作。
 * 给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。
 *
 * 提示：
 * 1 <= word1.length, word2.length <= 105
 * word1 和 word2 仅包含小写英文字母
 *
 */
public class CloseStrings {
    public static void main(String[] args) {
        System.out.println(closeStrings("abc" , "bca"));
    }
    /**
     * 思路 ：
     * （1）首先，使用辅助数组dp，来存储字符串word1和字符串word2中所有出现的字符的数量;
     * 若是word1和word2中的字符数量是不相等的话，则这两个字符串必然是不接近的;
     * （2）若是word2中所有字符皆是word1中出现过的字符 && 字符之间的数量个数是一致的,则这两个字符串是接近的;
     *
     * 注意 ：
     * 若是在word1中所出现的字符 在word2中未出现 || 在word2中所出现的字符 在word1中未出现的话，则都是false;
     * @param word1
     * @param word2
     * @return
     */
    public static boolean closeStrings(String word1, String word2) {
        // word1 和 word2 仅包含小写英文字母
        int[] dp1 = new int[26];
        int[] dp2 = new int[26];
        // 获取字符串word1中所有字符可能出现的情况;
        for (char ch : word1.toCharArray()) {
            dp1[ch - 'a']++;
        }
        // 获取字符串word2中所有字符可能出现的情况
        for (char ch : word2.toCharArray()) {
            dp2[ch - 'a']++;
        }
        // 不仅仅是word2出现word1中未出现的 && 也有可能是word1中出现word2中未出现的;
        for(int i = 0 ; i < 26 ; i++){
            // 若是在word1中所出现的字符 在word2中未出现 || 在word2中所出现的字符 在word1中未出现的话，则都是false;
            if((dp1[i] != 0 && dp2[i] == 0) || (dp2[i] != 0 && dp1[i] == 0)){
                return false;
            }
        }
        // 遍历dp1，去寻找word1中字符出现情况 ：是否与word2中字符出现情况一致;
        for(int i = 0 ; i < 26 ; i++){
            if( dp1[i] != 0){
                // 遍历dp1中所有不等于0的元素，即所有在字符串word1中出现过的字符;
                boolean flag = true;
                // 若是该元素在dp2中能够找到与之数量对应的，则继续遍历;否则直接返回false;
                for(int j = 0 ; j < 26 ; j++){
                    if(dp2[j] != 0 && dp1[i] == dp2[j]){
                        // 需要将dp2中对应元素置为0;
                        dp2[j] = 0;
                        flag = false;
                        break;
                    }
                }
                // 若是未能够在dp2数组中，找到与 当前遍历的dp1中元素一致的元素的话，直接返回false;
                if(flag){
                    return false;
                }
            }
        }
        // 若是上述情况都不满足，那么这两个字符串必然是接近的;
        return true;
    }
}
